#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author: zzll0909
# @file: 69.py
# @time: 2025/5/26
# @software: PyCharm

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            result = x
        elif x <= 3:
            result = 1
        else:
            lp = 2
            rp = x // 2
            result = 0
            while lp <= rp:
                mid = (lp + rp) // 2
                if mid ** 2 <= x:
                    result = mid
                    lp = mid + 1
                else:
                    rp = mid - 1
        return result


if __name__ == "__main__":
    pass
